import math
import sys
from heapq import heappush, heappop
from RandomList import GetRandomList
arr = []

# 利用heapq快速进行堆排
def heapsort():
	global arr
	h = []
	for value in arr:
		heappush(h, value)
	arr = []
	arr = arr + [heappop(h) for i in range(len(h))]

# 长度16以下进行插入排序
def InsertionSort(begin, end):
    
	left = begin
	right = end
	for i in range(left + 1, right + 1):
		key = arr[i]

		j = i - 1
		while j >= left and arr[j] > key:
			arr[j + 1] = arr[j]
			j = j - 1
		arr[j + 1] = key

# 快排 pivot是最后一个elem
def Partition(low, high):
	global arr
	pivot = arr[high]
	i = low - 1
	for j in range(low, high):
		if arr[j] <= pivot:
			i = i + 1
			(arr[i], arr[j]) = (arr[j], arr[i])
	(arr[i + 1], arr[high]) = (arr[high], arr[i + 1])
	return i + 1

# 取中间值
def MedianOfThree(a, b, d):
	global arr
	A = arr[a]
	B = arr[b]
	C = arr[d]

	if A <= B and B <= C:
		return b
	if C <= B and B <= A:
		return b
	if B <= A and A <= C:
		return a
	if C <= A and A <= B:
		return a
	if B <= C and C <= A:
		return d
	if A <= C and C <= B:
		return d

def IntrosortUtil(begin, end, depthLimit):
	global arr
	size = end - begin
	if size < 16:

		# if the data set is small, call insertion sort

		InsertionSort(begin, end)
		return

	if depthLimit == 0:

		# if the recursion limit is occurred call heap sort

		heapsort()
		return

	pivot = MedianOfThree(begin, begin + size // 2, end)
	(arr[pivot], arr[end]) = (arr[end], arr[pivot])

	partitionPoint = Partition(begin, end)

	IntrosortUtil(begin, partitionPoint - 1, depthLimit - 1)
	IntrosortUtil(partitionPoint + 1, end, depthLimit - 1)

# 计算递归深度然后判断是否需要操作
def Introsort(begin, end):

	depthLimit = 2 * math.floor(math.log2(end - begin))
	IntrosortUtil(begin, end, depthLimit)


def intro_sort_main(Arr):
	global arr
	arr = Arr + Arr		
	n = len(arr)
	Introsort(0, n - 1)


if __name__ == '__main__':
    Arr = GetRandomList(100)
    intro_sort_main(Arr)
    print(arr)
